#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int val) : val(val), next(nullptr) {}
};

class Solution {
public:
    ListNode* removeNthNodeFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;

        while(n-- && fast->next != nullptr) {
            fast = fast->next;
        }

        fast = fast->next; // fast提前多走一步，因为需要让slow指向删除节点的上一个节点
        while(fast) {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;
        return dummyHead->next;
    }

    /* 删除链表最后第n个节点 */
    /* 该方法是先遍历得到链表节点的个数 cnt，然后用总个数cnt 减去 n */
    /* 然后从前往后遍历到第 (cnt - n) 个节点，然后删掉该节点的下一个节点 就是要删除的节点 */ 
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        int cnt = 0;

        while(cur->next != nullptr) {
            cnt++;
            cur = cur->next;
        }

        int m = cnt - n;
        cur = dummyHead;
        while(m--) {
            cur = cur->next;
        }

        cur->next = cur->next->next;
        return dummyHead->next;
    }

};

ListNode* createNode(int val) {
    return (new ListNode(val));
}

void printNode(ListNode* head) {
    ListNode* cur = head;
    while(cur) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

int main(void) {
    ListNode* head = createNode(1);
    ListNode* node1 = createNode(2);
    ListNode* node2 = createNode(3);
    ListNode* node3 = createNode(4);
    ListNode* node4 = createNode(5);
    ListNode* node5 = createNode(6);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    printNode(head);

    Solution s;
    head = s.removeNthNodeFromEnd(head, 4);
    printNode(head);

    return 0;
}